/*--- quick5.c ---------------------------- Listing 5-11 --------
 * qsort() replacement derived from quick4.c
 * that may be used to replace your compiler's
 * version of qsort(). Just compile this routine
 * and then call xqsort() rather than qsort().
 *-------------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h> /* for rand() */
#include <string.h> /* for memcpy() */

typedef int ( *CF )();
#define A(x) (a + (x) * es)

static void InsertionSort ( char *a, int n, int es,
                            CF cf, char *b )
{
    int step, i;

    /* Look at 2nd thru Nth elements, putting each in place */
    for ( step = 1; step < n; step++ )
    {
        /* Now, look to the left and find our spot */
        memcpy ( b, A(step), es );
        for ( i = step - 1; i >= 0; i-- )
        {
            if ( cf ( A(i), b ) > 0 )
            {
                /* Not there yet, so make room */
                memcpy ( A(i+1), A(i), es );
            }
            else /* Found it! */
                break;
        }
        /* Now insert original value from Array[step] */
        memcpy ( A(i+1), b, es );

    }
}

static void xQuickSort5 ( char *a, int L, int R, int es,
                            CF cf, char *b )
{
    int diff;

    while (( diff = ( R - L )) >= 9 )  /* 10 elements a must */
    {
        int mid, i, j;
        char *ppivot;

        /* select a random mid element */
        mid = abs ( rand() ) % diff;
        if ( mid < 1 || mid > diff - 2 )
            mid = 1;
        mid += L;

        /*
         * Sort Lth, Rth, and middle element. Then swap the
         * middle element with the R-1'th element. This will
         * obviate the need for bound checking.
         */
        if ( cf ( A(L), A(mid) ) > 0 )
        {
            memcpy ( b, A(L), es );
            memcpy ( A(L), A(mid), es );
            memcpy ( A(mid), b, es );
        }
        if ( cf ( A(L), A(R) ) > 0 )
        {
            memcpy ( b, A(L), es );
            memcpy ( A(L), A(R), es );
            memcpy ( A(R), b, es );
        }
        if ( cf ( A(mid), A(R) ) > 0 )
        {
            memcpy ( b, A(mid), es );
            memcpy ( A(mid), A(R), es );
            memcpy ( A(R), b, es );
        }

        memcpy ( b, A(mid), es );
        memcpy ( A(mid), A(R-1), es );
        memcpy ( A(R-1), b, es );

        /*
         * Now, we know that Array[L] <= Array[R-1] <= Array[R].
         * We use Array[R-1] as the pivot, so this relationship
         * gives us known sentinels. Also, we need to partition
         * only between L+1 and R-2.
         */
        i = L;       /* Scan up from here */
        j = R - 1;   /* Scan down from here */
        ppivot = A ( j );
        for ( ;; )
        {

            /* Looking from left, find element >= Array[R-1] */
            while ( cf ( A(++i), ppivot ) < 0 )
                        ;

            /* Looking from right, find element <= Array[R-1] */
            while ( cf ( A(--j), ppivot ) > 0 )
                        ;

            if ( i >= j )
                break;

            /* swap ith and jth elements */
            memcpy ( b, A(i), es );
            memcpy ( A(i), A(j), es );
            memcpy ( A(j), b, es );
        }


        /* swap ith and the pivot */
        memcpy ( b, A(R-1), es );
        memcpy ( A(R-1), A(i), es );
        memcpy ( A(i), b, es );

        if ( i - L > R - i )    /* left half is larger */
        {
            xQuickSort5 ( a, i+1, R, es, cf, b );
            R = i - 1;
        }
        else  /* right half is larger */
        {
            xQuickSort5 ( a, L, i-1, es, cf, b );
            L = i + 1;
        }
    }
}

void xqsort ( char *a, int n, int es, CF cf )
{
    #define DEFAULT_BUFFER 64
    char buf[DEFAULT_BUFFER], *b;

    printf ( "sorting %d elements of size %d\n", n, es );

    /* allocate space for making a copy of an item */
    b = buf;
    if ( es > DEFAULT_BUFFER )
    {
        b = (char *) malloc ( es );
        if ( b == NULL )
        {
            qsort (a, n, es, cf );
            return;
        }
    }

    /* Quicksort to get nearly sorted file */
    xQuickSort5 ( a, 0, n - 1, es, cf, b );

    /* Do an insertion sort on the now nearly sorted file */
    InsertionSort ( a, n, es, cf, b );

    /* Cleanup */
    if ( b != buf )
        free ( b );
}
